SparseArray源码分析

发表于 | 分类于 | 阅读次数:

SparseArray，SparseIntArray,SparseBooleanArray等是Android官方提倡使用的高效数据结构。它同java中的HashMap类似属于存储键值对的集合，准确的来说是HashMap<Integer,V>。但同HashMap相比它更加轻量，执行效率更高。下面我们就对SparseArray的源码进行解读，了解它内部的执行原理。

构造方法

源码位置：

frameworks/base/core/java/android/util/SparseArray.java

首先我们从其构造函数入手

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class SparseArray<E> implements Cloneable {
	 
	 private static final Object DELETED = new Object();
	 private boolean mGarbage = false;
	
	 private int[] mKeys;
	 private Object[] mValues;
	 private int mSize;

	public SparseArray() {
	        this(10);
	}
	
	public SparseArray(int initialCapacity) {
	        if (initialCapacity == 0) {
	            mKeys = ContainerHelpers.EMPTY_INTS;
	            mValues = ContainerHelpers.EMPTY_OBJECTS;
	        } else {
	            initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
	            mKeys = new int[initialCapacity];
	            mValues = new Object[initialCapacity];
	        }
	        mSize = 0;
	}
	……
}

初始化时传递的initialCapacity大小为10，但这个只是一个参考值，随后又通过ArrayUtils.idealIntArraySize对初始值进行了调整，从函数名字上看这个方法会根据参考值返回一个比较理想容量大小。我们看看它是如何计算的

1
2
3
4
5
6
7
8
9
10
11
public static int idealIntArraySize(int need) {
        return idealByteArraySize(need * 4) / 4;
}

public static int idealByteArraySize(int need) {
        for (int i = 4; i < 32; i++)
            if (need <= (1 << i) - 12)
                return (1 << i) - 12;

        return need;
}

计算的结果是一个2的幂次方的数减去12，对于SparseArray还需要再除以4作为结果返回，这里返回的值为(1<<6-12)/4 = 13 。

这里有个疑惑就是为什么需要对初始值进行重新计算得到SparseArray的容量大小？

获取元素

可以看出SparseArray内部是通过数组来实现的，相比hashMap的hash表和链表要轻量一些。我们先看看它的get方法如何实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public E get(int key) {
        return get(key, null);
}

public E get(int key, E valueIfKeyNotFound) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

内部逻辑非常简单，通过key来进行二分查找，这么说键值在mKeys中的存储是有序的。这就要求在添加元素中做保证。这里二分搜索的结果是key值所在的索引值i，这个索引在mValues中对应的数据就是key对应的值，可见mKeys和mValues是一一对应的，只是分别存储在两个数组中罢了。这里如果查找到会返回索引值i，如果i小于0说明没有找到，同时如果i所在的value已经失效即为DELETE，则也算没有找到value值，返回默认的valueIfKeyNotFound，否则返回mValues[i]作为结果。

frameworks/base/core/java/android/util/ContainerHelpers.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;

        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
}

二分搜索，这里就不需要做解释了，需要注意的是如果找到了key值，则返回其在array中的索引mid，否则返回~lo，lo代表了所查找key值所应该存在的位置，这里取反是为了说明key值不存在该位置，但如果需要添加key值对应的value就可以将其放在lo处。

添加元素

我们知道二分搜索是基于有序序列进行的操作，那么在我们添加元素也就是put时需要保证数组的有序性，我们接下来看看put的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;

        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        if (mGarbage && mSize >= mKeys.length) {
            gc();

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }

        if (mSize >= mKeys.length) {
            int n = ArrayUtils.idealIntArraySize(mSize + 1);

            int[] nkeys = new int[n];
            Object[] nvalues = new Object[n];

            // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);

            mKeys = nkeys;
            mValues = nvalues;
        }

        if (mSize - i != 0) {
            // Log.e("SparseArray", "move " + (mSize - i));
            System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
            System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
        }

        mKeys[i] = key;
        mValues[i] = value;
        mSize++;
    }
}

  1. put同样一开始先binarySearch查找key值是否已经存在，如果存在，只需更新索引i处的value。

  2. 否则我们对i进行取反，这里取反后的i值我们知道就是key值应该存放的位置。
    随后判断i是否小于mSize 且 mValues对应i处的值已经失效，如果失效了就直接替换该处的值即可。否则看是否需要进行gc(看mGarbage是否置为true且当前的数组已经满了)，这里的gc是指对失效元素进行回收，并重新计算大小。gc完后会再次计算key值索引，因为数组大小可能发生了变化。

  3. 如果gc后数组依旧时满的，这就需要我们再开辟空间了，同样调用ArrayUtils.idealIntArraySize重新计算容量，然后创建数组，并将mKeys和mValues拷贝到新的数组中。

  4. 如果mSize-i！=0 说明要在数组间插入key值，这个需要将索引i后的元素统一向后挪动一个位置为key值腾出一个位置。

  5. 将key值对应的value分别放在mKeys和mValues中并递增mSize。

gc的回收策略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void gc() {
    int n = mSize;
    int o = 0;
    int[] keys = mKeys;
    Object[] values = mValues;

    for (int i = 0; i < n; i++) {
        Object val = values[i];

        if (val != DELETED) {
            if (i != o) {
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null;
            }

            o++;
        }
    }

    mGarbage = false;
    mSize = o;
}

gc负责将已经清理失效的value(即等于DELETED)，并重新计算mSize。

在SparseArray的众多方法中都有可能调用gc方法比如size,keyAt,valueAt等等，以此来分摊可能进行的gc的执行时间。

在SparseArray中还有一个比put更加高效的方法append,它首先判断key值是否比数组末尾的key值还要大，如果是的话就只需将其添加到末尾就行了，因为它保证了有序性。否则就调用put来添加该key-value。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public void append(int key, E value) {
    if (mSize != 0 && key <= mKeys[mSize - 1]) {
        put(key, value);
        return;
    }

    if (mGarbage && mSize >= mKeys.length) {
        gc();
    }

    int pos = mSize;
    if (pos >= mKeys.length) {
        int n = ArrayUtils.idealIntArraySize(pos + 1);

        int[] nkeys = new int[n];
        Object[] nvalues = new Object[n];

        // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
        System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
        System.arraycopy(mValues, 0, nvalues, 0, mValues.length);

        mKeys = nkeys;
        mValues = nvalues;
    }

    mKeys[pos] = key;
    mValues[pos] = value;
    mSize = pos + 1;
}

SparseArray的delete方法同样是它高效的体现，它并不真正的将key-value从数组中移除，而仅仅是将value标记为失效，同时把mGarbage置为true代表需要进行gc,这样做原因是，随后可能存在key值又加入进来的情况，这样我们就仅需将已经失效的元素换成我们添加的value值即可，可以参见Put方法的第二步说明。这样避免了数组的频繁抖动引起的性能问题。

1
2
3
4
5
6
7
8
9
public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}
坚持原创技术分享，您的支持将鼓励我继续创作！